Remove Nth Node From End of List

Leetcode #19 | Medium | Связный список | Быстрый и медленный

Идея

Идея быстрого и медленного указателя. Сначала ставим tail на k-ую ноду (начиная с 0). Теперь между указателем на первую и tail расстояние ровно k. Значит, когда мы додвинем tail до null, указатель станет ровно на ноде, которую нужно удалить по условию. Вместе с движением до null заводим еще и prev начиная с null. Затем удаляем как prev.next = cur.next
Важно: если после передвижения tail на k мы же на null то просто возвращаем head.next, так как получается что нам надо удалить голову, а все что после головы оставить.

Big-O

• Время O(N)
• Память O(1)

Код

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy, right = head;
        for (int i = 0; i < n; i++) right = right.next;
        while (right != null) { left = left.next; right = right.next; }
        left.next = left.next.next;
        return dummy.next;
    }
}